16 August 1998

Date: Sun, 16 Aug 1998 08:53:37 -0500
To: cypherpunks@toad.com
From: Bruce Schneier <schneier@counterpane.com>
Subject: Announcement: Cryptanalysis of Frog (an AES Candidate)

                    Results Announcement:

D. Wagner, N. Ferguson, and B. Schneier, "Cryptanalysis of Frog," 
Counterpane Systems Report, Aug 1998.

                         Abstract:
We examine some attacks on the FROG cipher.  First we give a 
differential attack which uses about $2^{58}$ chosen plaintexts and 
very little time for the analysis; it works for about $2^{-33.0}$ of 
the keyspace.  Then we describe a linear attack which uses $2^{56}$ 
known texts and works for $2^{-31.8}$ of the keyspace.  The linear 
attack can also be converted to a ciphertext-only attack using $2^{64}$ 
known ciphertexts.  Also, the decryption function of FROG is a lot 
weaker than the encryption function.  We show a differential attack 
on the decryption function that requires $2^{36}$ chosen ciphertexts 
and works on $2^{-29.3}$ of the keyspace.  Using our best attack an 
attacker with a sufficient number of cryptanalytical targets can expect 
to recover his first key after $2^{56.7}$ work.  Taken together, these 
observations suggest that FROG is not a very strong candidate for the 
AES. 


This paper is available at http://www.counterpane.com/publish.html, and 
will be made available at the AES Workshop next week.

Cheers,
Bruce 
**********************************************************************
Bruce Schneier, President, Counterpane Systems     Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN  55419      Fax: 612-823-1590
           Free crypto newsletter.  See:  http://www.counterpane.com